//
// Created by f12160c on 2018/7/25.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#include "leetcode/leetcode.hpp"

using namespace std;

vector<vector<int>> Solution::fourSum(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<int>> ret;
    unordered_map<int, vector<pair<int, int>>>  reverse_map;
    if(n < 4){
        return ret;
    }
    int twoSums[n][n];

    sort(nums.begin(), nums.end());
    for(int i = 0; i < n; i++) {
        for(int j =  i + 1; j < n; j++) {
            twoSums[i][j] = nums[i] + nums[j];
            auto got = reverse_map.find(twoSums[i][j]);
            if(got == reverse_map.end())
            {
                reverse_map.insert(make_pair(twoSums[i][j], vector{make_pair(i, j)}));
            }
            else
            {
                reverse_map[twoSums[i][j]].push_back(make_pair(i, j));
            }
        }
    }

    int last[4];
    last[0] = nums[0] + 1;
    for(int i = 0; i < n; i++) {
        if (last[0] == nums[i]) {
            continue;
        }
        last[0] = nums[i];
        last[1] = nums[i + 1] + 1;
        for (int j = i + 1; j < n; j++) {
            if (last[1] == nums[j]) {
                continue;
            }
            last[1] = nums[j];
            last[2] = target - last[0] - last[1];
            last[3] = 1;

            int tmp = target - twoSums[i][j];
            auto got = reverse_map.find(tmp);
            if(got != reverse_map.end())
            {
                for(auto & index_pair : reverse_map[tmp])
                {
                    if(index_pair.first > j)
                    {
                        if ((last[2] == nums[index_pair.first]) && (last[3] == nums[index_pair.second])) {
                            continue;
                        }
                        last[2] = nums[index_pair.first];
                        last[3] = nums[index_pair.second];
                        ret.push_back(vector{nums[i], nums[j], nums[index_pair.first], nums[index_pair.second]});
                    }
                }
            }
        }
    }

    return ret;
}

